package io.adrainty.algorithm.leetcode.lcr;

import java.util.*;

/**
 * LCR 016. 无重复字符的最长子串
 * @link <a href="https://leetcode.cn/problems/wtcaE1/description/">...</a>
 * @author adrainty
 * @version v1.0.0
 * @since 2024/12/20 下午3:52
 */
public class LCR016 {

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) return 0;
        Set<Character> distance = new HashSet<>();
        int ans = 1;
        distance.add(s.charAt(0));
        LinkedList<Character> queue = new LinkedList<>();
        queue.offer(s.charAt(0));

        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!distance.contains(c)) {
                distance.add(c);
                ans = Math.max(ans, queue.size());
            } else {
                while (!queue.isEmpty()) {
                    Character character = queue.pollFirst();
                    distance.remove(character);
                    if (character == c) break;
                }
                distance.add(c);
            }
            queue.offerLast(c);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb"));
        System.out.println(lengthOfLongestSubstring("bbbbb"));
        System.out.println(lengthOfLongestSubstring("pwwkew"));
        System.out.println(lengthOfLongestSubstring("bbtablud"));
    }

}
